package com.liunian.test;

public class ShortestPalindrome {

	public String shortestPalindrome(String s) {
		char[] chars = s.toCharArray();
		int n = s.length();
		int[] next = new int[n];
		int j = 0;
		for (int i = 1; i < n; i++) {
			while (j > 0 && chars[j] != chars[i]) {
				j = next[j - 1];
			}
			if (chars[i] == chars[j]) {
				j++;
			}
			next[i] = j;
		}
		int best = 0;
		for (int i = n - 1; i >= 0; i--) {
			while (best > 0 && chars[best] != chars[i]) {
				best = next[best - 1];
			}
			if (chars[best] == chars[i]) {
				best++;
			}
		}
		String s1 = new String(chars, best, n - best);
		return new StringBuilder(s1).reverse().append(s).toString();
	}

	public static void main(String[] args) {
		ShortestPalindrome shortestPalindrome = new ShortestPalindrome();
		System.out.println(shortestPalindrome.shortestPalindrome("abcd"));
	}

}
